package com.leecode.xiehf.page_02;

import com.leecode.Printer;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 *
 * https://leetcode-cn.com/problems/maximum-subarray/
 */
public class Solution_0053 extends Printer {

    public static void main(String[] args) {
        Solution_0053 solution = new Solution_0053();
        int s = solution.maxSubArray(new int[]{-2,1});
        print(s);
    }

    public int maxSubArray(int[] nums) {
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        int sum = 0;
        int res = nums[0];
        for (int num : nums) {
            // 如果之前大于0 那么序列记录增加长度
            if (sum > 0) {
                sum += num;
            } else {
                // 否则重新开始，因为之前小于0，所有前面的都不利于后面
                sum = num;
            }
            res = Math.max(sum, res);
        }
        return res;
    }

    public int maxSubArray1(int[] nums) {
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        int[][] dp = new int[length][length];
        for (int i = 0; i < length; i++) {
            dp[i][i] = nums[i];
        }
        int max = dp[0][0];
        for (int i = 0; i < length; i++) {
            for (int j = i; j < length; j++) {
                if (j > 0) {
                    dp[i][j] = dp[i][j - 1] + nums[j];
                    if (dp[i][j] > max) {
                        max = dp[i][j];
                    }
                }
            }
        }
        return max;
    }

}
